{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "899a32c3-c074-4be2-b445-3e51a330791b",
   "metadata": {},
   "source": [
    "物联网与大数据第六章作业  \n",
    "姚龙飞"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "414e79a8-2902-481f-9b05-ae0eaa35d1d0",
   "metadata": {},
   "source": [
    "# 第6章 关联分析：基本概念和算法"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e08e83d3-89d2-48b6-af53-3c2e0f367219",
   "metadata": {},
   "source": [
    "m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c019edb-8754-49b1-a6c4-e63c8e5aaf51",
   "metadata": {},
   "source": [
    "## 6.1 问题定义\n",
    "\n",
    "### 6.1.1 基本术语\n",
    "\n",
    "- **事务数据集**：一系列事务的集合，每个事务包含一组项。\n",
    "- **项集**：包含一个或多个项的集合，如果包含k个项，则称为k项集。\n",
    "- **支持度**：项集在所有事务中出现的频率。\n",
    "- **置信度**：在包含X的事务中也包含Y的条件概率。\n",
    "\n",
    "### 6.1.2 形式化描述\n",
    "\n",
    "- **二元表示**：事务数据可以用二元变量表示，如果项在事务中出现则为1，否则为0。\n",
    "- **项集的支持度计数**：包含特定项集的事务个数。\n",
    "- **关联规则**：形如X→Y的蕴涵表达式，表示在包含X的事务中也倾向于包含Y。\n",
    "\n",
    "### 6.1.3 重要公式\n",
    "\n",
    "- **支持度计算**：\n",
    "  \n",
    " $$\n",
    "  s(X) = \\frac{o(X)}{N}\n",
    "  $$ \n",
    "  其中， $s(X)$ 是项集X的支持度， $o(X)$ 是项集X的支持度计数，N是事务总数。\n",
    "\n",
    "- **置信度计算**：\n",
    "  \n",
    " $$\n",
    "  c(X \\rightarrow Y) = \\frac{o(X \\cup Y)}{o(X)}\n",
    "  $$ \n",
    "  其中， $c(X \\rightarrow Y)$ 是从X到Y的规则的置信度， $o(X \\cup Y)$ 是X和Y的联合支持度计数。\n",
    "\n",
    "## 6.2 频繁项集的产生\n",
    "\n",
    "### 6.2.1 Apriori算法\n",
    "\n",
    "- **Apriori原理**：如果一个项集是频繁的，则它的所有非空子集也必须是频繁的。\n",
    "- **算法步骤**：\n",
    "  1. 计算所有单个项的支持度。\n",
    "  2. 基于最小支持度阈值，找出所有频繁1-项集。\n",
    "  3. 利用频繁k-项集生成候选k+1-项集。\n",
    "  4. 计算候选项集的支持度，并过滤出频繁项集。\n",
    "  5. 重复步骤3和4，直到不能找到新的频繁项集。\n",
    "\n",
    "### 6.2.2 候选项集的产生与剪枝\n",
    "\n",
    "- **产生**：通过合并频繁(k-1)-项集来生成候选k-项集。\n",
    "- **剪枝**：基于支持度的反单调性，剪枝掉那些非频繁的候选项集。\n",
    "\n",
    "### 6.2.3 支持度计数\n",
    "\n",
    "- **计数方法**：将每个事务中的项集与候选项集进行比较，更新支持度计数。\n",
    "\n",
    "### 6.2.4 计算复杂度\n",
    "\n",
    "- **影响因素**：支持度阈值、项数、事务数和事务的平均宽度。\n",
    "\n",
    "## 6.3 规则产生\n",
    "\n",
    "### 6.3.1 基于置信度的剪枝\n",
    "\n",
    "- **定理**：如果规则X→Y-X不满足置信度阈值，则形如X→Y-X'的规则一定不满足置信度阈值，其中X是X的子集。\n",
    "\n",
    "### 6.3.2 Apriori算法中规则的产生\n",
    "\n",
    "- **过程**：从频繁项集中提取高置信度的规则。\n",
    "\n",
    "## 6.4 频繁项集的紧凑表示\n",
    "\n",
    "### 6.4.1 极大频繁项集\n",
    "\n",
    "- **定义**：频繁项集，其直接超集都不是频繁的。\n",
    "\n",
    "### 6.4.2 闭频繁项集\n",
    "\n",
    "- **定义**：项集X是闭的，如果它的直接超集都不具有和它相同的支持度计数。\n",
    "\n",
    "## 6.5 产生频繁项集的其他方法\n",
    "\n",
    "- **FP增长算法**：使用FP树结构来压缩数据集，并从中提取频繁项集。\n",
    "\n",
    "## 6.6 关联模式的评估\n",
    "\n",
    "### 6.6.1 兴趣度的客观度量\n",
    "\n",
    "- **支持度、置信度、提升度、兴趣因子**：用于评估关联模式的质量。\n",
    "\n",
    "### 6.6.2 兴趣度的主观度量\n",
    "\n",
    "- **基于领域知识**：模式是否有趣取决于它是否提供了新的、有用的信息。\n",
    "\n",
    "### 6.6.3 客观度量的性质\n",
    "\n",
    "- **反演性、零加性、缩放不变性**：评估客观度量的标准。\n",
    "\n",
    "## 6.7 关联模式的评估\n",
    "\n",
    "### 6.7.1 客观兴趣度度量\n",
    "\n",
    "- **零加性**：客观度量M在零加操作下是不变的，即增加 $f_{00}$ 而保持相依表中所有其他的频度不变并不影响M的值。满足零加性的度量包括余弦（IS）和Jaccard度量，而不满足该性质的度量包括兴趣因子、PS、几率和系数。\n",
    "\n",
    "- **缩放性**：客观度量M在行/列缩放操作下是不变的，如果 $M(T) = M(T')$ ，其中 $T$ 是频度计数为\n",
    " $$f_{11}, f_{00}, f_{10}, f_{01}$$ 的相依表， $T'$ 是频度计数为\n",
    " $$k_1k_3f_{11}, k_2k_3f_{10}, k_1k_4f_{01}, k_2k_4f_{00}$$ 的相依表。\n",
    "\n",
    "### 6.7.2 多个二元变量的度量\n",
    "\n",
    "- **多维相依表**：使用多维相依表，可以扩展到多个变量。例如，表6-18显示了a，b和c的3维相依表，每个表目 $f$ 都表示包含项a,b和c的某种组合的事务数。\n",
    "\n",
    "### 6.7.3 辛普森悖论\n",
    "\n",
    "- **辛普森悖论**：解释变量之间的关联时要特别小心，因为观察到的联系可能受其他混淆因素的影响，这些因素可能导致观察到的一对变量之间的联系消失或逆转方向。\n",
    "\n",
    "## 6.8 倾斜支持度分布的影响\n",
    "\n",
    "### 6.8.1 倾斜支持度分布的定义\n",
    "\n",
    "- **倾斜支持度分布**：许多关联分析算法的性能受输入数据的性质的影响。具有倾斜支持度分布的数据集，其中大多数项具有较低或中等频率，但是少数项具有很高的频率。\n",
    "\n",
    "### 6.8.2 交叉支持模式\n",
    "\n",
    "- **交叉支持模式的定义**：交叉支持模式是一个项集 $X=\\{i_1,i_2,...,i_k\\}$ ，它的支持度比率小于用户指定的阈值 $h_c$ 。支持度比率定义为 $r=\\min\\{s(i_1),s(i_2),...,s(i_k)\\}/\\max\\{s(i_1),s(i_2),...,s(i_k)\\}$ 。\n",
    "\n",
    "### 6.8.3 h置信度\n",
    "\n",
    "- **h置信度**：用于消除交叉支持模式，确保项集之间的强关联。h置信度是全置信度度量，它要求项集中的项之间是强关联的。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
